The subject matter discussed in the background section should not be assumed to be prior art merely as a result of its mention in the background section. Similarly, a problem mentioned in the background section or associated with the subject matter of the background section should not be assumed to have been previously recognized in the prior art. The subject matter in the background section merely represents different approaches, which in and of themselves may also correspond to embodiments of the claimed subject matter.
Squaring and multiplication are the most critical widely used functions in the context of large integer arithmetic performed by processors (e.g., CPUs, processing cores, etc.). Large integer arithmetic is used in various libraries for High Performance Computing (HPC) applications such as the GNU Multiple Precision Arithmetic Library (GMP). Moreover, squaring and multiplication forms the basis of all asymmetric cryptographic algorithms, including, for example, RSA (RSA is not an acronym, but rather represents the initials of the inventors' surnames: Ron Rivest, Adi Shamir, and Leonard Adleman), Digital Signature Algorithm (DSA), Diffie-Hellman key exchange (D-H or DH), Elliptic Curve Cryptography (ECC), etc.
RSA is an algorithm for public-key cryptography that is based on the presumed difficulty of factoring large integers. A user of RSA creates and then publishes the product of two large prime numbers, along with an auxiliary value, as their public key. The prime factors must be kept secret. Anyone can use the public key to encrypt a message, but if the public key is large enough, only someone with knowledge of the prime factors can feasibly decode the message.
Large integer Multiplication and Squaring are computationally intensive problems on general-purpose processors such as IA (Intel Architecture processors) and applications such as OpenSSL (Open Source Secure Sockets Layer) and GMP often optimize for single digit performance gains.
Multiple precision arithmetic indicates that calculations are performed on numbers for which digits of precision are limited only by the available memory of the host system. This contrasts with the faster fixed-precision arithmetic which typically offers between 16 and 64 bits of precision.
Given the ubiquity of the squaring and multiplication functions by processors for the sake of security, cryptography, key exchange, RSA signature creation and verification, etc., any efficiency gains, even minor performance improvements, are highly valued to those having skill in the art and are further valued to the computing market place which benefits generally from such efficiency improvements.
The present state of the art may therefore benefit from the methods and apparatuses for implementing fast large-integer arithmetic on IA (Intel Architecture) processors as described herein.